package com.maozzi.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 双指针法
 *
 * @author maozi
 */
public class DoublePointer {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2};
//        System.out.println(removeElement(arr, 2));
//        System.out.println(removeDuplicates(arr));

//        moveZeroes(new int[]{0, 1, 0, 3, 12});
//        System.out.println(generateMatrix(3));
        System.out.println(spiralOrder(new int[][]{{6, 9, 7}}));
    }

    /**
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
     * 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
     * <p>
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     * <p>
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
     * 返回 k。
     */
    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    /**
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
     * 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * <p>
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * <p>
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     */
    public static int removeDuplicates(int[] nums) {
        int fast = 1;
        int slow = 1;
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * <p>
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     */
    public static void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }

        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * <p>
     * 找出该数组中满足其总和大于等于 target 的长度最小的
     * 子数组
     * [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                min = Math.min(min, i - left + 1);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    /**
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     */
    public static int[][] generateMatrix(int n) {
        int[][] arr = new int[n][n];
        int loop = n / 2;
        int offset = 1;
        int x = 0;
        int y = 0;
        int i, j;
        int val = 1;
        while (loop-- > 0) {
            for (j = y; j < n - offset; j++) {
                arr[x][j] = val++;
            }
            for (i = x; i < n - offset; i++) {
                arr[i][j] = val++;
            }
            for (; j > y; j--) {
                arr[i][j] = val++;
            }
            for (; i > x; i--) {
                arr[i][y] = val++;
            }
            x++;
            y++;
            offset++;
        }
        if (n % 2 == 1) {
            arr[x][y] = val;
        }
        return arr;
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();

        int m = matrix.length;
        int n = matrix[0].length;
        int offset = 1;
        int x = 0, y = 0;
        int i, j;

        while (offset <= m && offset <= n) {
            for (j = y; j < n - offset; j++) {
                list.add(matrix[x][j]);
            }
            for (i = x; i < m - offset; i++) {
                list.add(matrix[i][j]);
            }
            for (; j > y ; j--) {
                list.add(matrix[i][j]);
            }
            for (; i > x; i--) {
                list.add(matrix[i][y]);
            }
            x++;
            y++;
            offset++;
        }
        if (m == n && m % 2 == 1) {
            list.add(matrix[x][y]);
        }

        return list;
    }
}
